一、 題目介紹
今天要練習的題目是 LeetCode 509：Fibonacci Number（費波那契數）

費波那契數列的定義如下

• F(0) = 0
• F(1) = 1
• F(n) = F(n - 1) + F(n - 2)
  也就是從第三個數字開始，每一項都是前兩項相加

例如：
F(0) = 0
F(1) = 1
F(2) = 1
F(3) = 2
F(4) = 3
F(5) = 5

因此，如果輸入n = 4
答案就是3

二、解題思路
如果直接使用遞迴fib(n) = fib(n - 1) + fib(n - 2)
雖然很符合費波那契數列的定義，但是會產生大量重複計算

例如計算fib(5)時

可以看到fib(3)、fib(2)等結果會被重複計算
因此這次使用Dynamic Programming，把已經算過的結果保存起來

我們定義dp[i] = F(i)也就是dp[i]代表第i個費波那契數

接著根據題目的公式：dp[i] = dp[i - 1] + dp[i - 2]
只需要從小到大依序計算即可

三、Dynamic Programming流程
以 n = 5 為例
dp[0] = 0
dp[1] = 1

dp[2] = dp[1] + dp[0] = 1
dp[3] = dp[2] + dp[1] = 2
dp[4] = dp[3] + dp[2] = 3
dp[5] = dp[4] + dp[3] = 5

最後得到dp[5] = 5
所以答案為5
這種方法最大的優點，就是每個Fibonacci數只需要計算一次

四、Java實作

五、Python實作

六、空間最佳化
觀察前面的程式可以發現，在計算dp[i]時，其實只需要前兩個結果
也就是dp[i - 2]、dp[i - 1]
並不需要保留完整的dp陣列
因此可以將空間從O(n)優化成O(1)

七、時間與空間複雜度
Java / Python DP 陣列版本

• 時間複雜度：O(n)
  • 從2一直計算到n，每個數字只處理一次。
• 空間複雜度：O(n)
  • 需要建立大小為n + 1的dp陣列。

空間最佳化版本

• 時間複雜度：O(n)
  • 仍然需要從2計算到n。
• 空間複雜度：O(1)
  • 只使用prev2、prev1和current等固定數量的變數。

八、Java與Python解法比較

九、今日學習心得
今天透過Fibonacci Number進一步理解Dynamic Programming的概念。Fibonacci數列本身是一個很經典的遞迴問題，但如果直接使用遞迴方式計算，會產生大量重複運算，因此可以利用DP將已經計算過的結果保存下來，將效率提升到O(n)。

另外，我也學習到DP除了可以使用陣列保存所有狀態之外，如果仔細觀察狀態轉移關係，有時候只需要保留前幾個狀態，就能進一步將空間複雜度最佳化到O(1)。

透過Day 17的Climbing Stairs和今天的Fibonacci Number，我也發現相同的狀態轉移公式可以出現在不同問題中，但真正重要的是理解每個狀態所代表的意義。這讓我對Dynamic Programming的理解不再只是套公式，而是開始學習如何自己定義狀態與找出轉移關係。